package 回溯算法;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author: biubiu0002
 * @Date: 2021-03-25 17:38
 **/
public class 解数独 {
    class Node{
        public int i;
        public int j;
        public char x;

        public Node(int i, int j, char x) {
            this.i = i;
            this.j = j;
            this.x = x;
        }
    }


    public void solveSudoku(char[][] board) {
        int n =board.length;
        LinkedList<Node> nodeList = new LinkedList<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){

                if(board[i][j]=='.'){
                    Node node = new Node(i,j,board[i][j]);
                    nodeList.add(node);
                }


            }


        }
        backtrace(board,0,nodeList);



    }

    //选择列表1~9
    //路径 board
    //basecase 填完整个board
    boolean backtrace(char[][] board,int index,LinkedList<Node> nodeList){

        int n =nodeList.size();
        for(int i=1;i<=9;i++){



            Node node = nodeList.get(index);
            //排除不合法选择
            node.x=(char) ('0'+i);
            if(!isValid(board,node)){
                continue;
            }

            int nodei=node.i;
            int nodej=node.j;
            //做选择
            board[nodei][nodej]=(char)('0'+i);

            //终止条件:完成了最后一个填空。
            if(index==nodeList.size()-1)
                return true;

            //下一层
            boolean isDone = backtrace(board, index+1, nodeList);
            //如果已经完成最后一个空，就保存该现场，不要撤销选择。
            if(isDone)
                return true;

            //撤销选择
            board[nodei][nodej]='.';


        }

        return false;


    }

    boolean isValid(char[][] board, Node node){
        int nodei = node.i;
        int nodej = node.j;
        char nodex = node.x;
        int nodeiKuai = nodei/3;
        int nodejKuai = nodej/3;

        //判断node所在行有无重复
        for(int j=0;j<9;j++){
            if(j==nodej)
                continue;
            if(board[nodei][j]=='.')
                continue;

            if(board[nodei][j]==nodex)
                return false;
        }

        //判断node所在列有无重复
        for(int i=0;i<9;i++){
            if(i==nodei)
                continue;
            if(board[i][nodej]=='.')
                continue;

            if(board[i][nodej]==nodex)
                return false;
        }

        for(int i=nodeiKuai*3;i<nodeiKuai*3+3;i++){
            for(int j=nodejKuai*3;j<nodejKuai*3+3;j++){
                if(i==nodei&&j==nodej)
                    continue;

                if(board[nodei][j]=='.')
                    continue;
                if(board[i][j]==nodex)
                    return false;

            }

        }
        return true;

    }



    public static void main(String[] args) {
        char[][] nums={{'5','3','.','.','7','.','.','.','.'},
                {'6','.','.','1','9','5','.','.','.'},
                {'.','9','8','.','.','.','.','6','.'},
                {'8','.','.','.','6','.','.','.','3'},
                {'4','.','.','8','.','3','.','.','1'},
                {'7','.','.','.','2','.','.','.','6'},
                {'.','6','.','.','.','.','2','8','.'},
                {'.','.','.','4','1','9','.','.','5'},
                {'.','.','.','.','8','.','.','7','9'}};
        解数独 test = new 解数独();
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++)
                System.out.print(nums[i][j]+" ");
            System.out.println();
        }
        test.solveSudoku(nums);




        System.out.println("------------------nums--------------------");
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++)
                System.out.print(nums[i][j]+" ");
            System.out.println();
        }
    }


}
